## 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
from math import sqrt
import timeit
# 未优化的朴素求法的时间复杂度是O(N^2)。
def isPrime(num):
    if num==2:
        return True
    if num<=1 or num%2==0: #将除 2 之外的偶数排除，大大减少了执行时间。
        return False
    for i in range(3,int(num**0.5)+1,2):
        if num%i==0:
            return False
    return True

def isPrime6(num): ##66
    if num%2==0 or num<5:
        if num in [2,3]:
            return True
        return False
    elif num % 6 == 1 or num % 6 == 5:
        for i in range(3,int(num**0.5)+1,2):
            if num % i == 0:
                return False
        else:
            return True
    else:
        return False

def outlist():
    tt,ff=[],[]
    for i in range(100):
        if isPrime(i):
            tt.append(i)
            # print(i,isPrime6(i),end='\t')
        # else:
        #     ff.append(i)

    print("质数表",*tt)



def test_long(num):
    print(f"{num}\nisPrime judge:{isPrime(num)}\nisPrime6 judge:{isPrime6(num)}")




if __name__=="__main__":

    t=timeit.timeit(stmt="isPrime(20190523)",setup="from isprime import isPrime",number=1000) 
    t6=timeit.timeit(stmt="isPrime6(20190523)",setup="from isprime import isPrime6",number=1000) 
    print(t,t6,sep="\n")
    test_long(20190523)
    # outlist()

# 0.20712345700303558
# 0.15111990099831019